# 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。


class Solution:
    def maxSubArray(self, nums) -> int:
        fu_max_num = nums[0]
        try:
            while nums[0] <= 0:
                fu_max_num = max(nums.pop(0), fu_max_num)
            while nums[-1] <= 0:
                nums.pop(-1)
        except:
            return fu_max_num
        i, j, sum_i, sum_j = 0, len(nums) - 1, 0, 0
        max_i, max_j, res = nums[i], nums[j], 0
        while i <= len(nums) - 1:
            sum_i += nums[i]
            sum_j += nums[j]
            if sum_i >= max_i:
                max_i = sum_i
                tar_i = i
            if sum_j >= max_j:
                max_j = sum_j
                tar_j = j
            i += 1
            j -= 1
        if tar_i < tar_j:
            sum_i, res_i = 0, 0
            sum_j, res_j = 0, 0
            for i in range(tar_j, len(nums)):
                sum_i += nums[i]
                res_i = max(res_i, sum_i)
            j = tar_i
            while j >= 0:
                sum_j += nums[j]
                res_j = max(res_j, sum_j)
                j -= 1
            return max(res_j, res_i)
        else:
            for h in range(tar_j, tar_i+1):
                res += nums[h]
        return res


a = Solution()
print(a.maxSubArray([-1, -1, -2, -2]))